package leetcode;

import java.util.Arrays;

/**
 * @Description 制作 m 束花所需的最少天数
 * f(index,m) = max( a[i]+a[i-1]...a[i-k] , f(index-k-1,m-1))
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.5.9
 */

public class T1482 {

    public static void main(String[] args) {
        T1482 t1482 = new T1482();
        int[] bloomDay = {1,10,3,10,2};
        int m = 3;
        int k = 1;
        System.out.println(t1482.minDays(bloomDay, m, k));
    }

    /**
     * 直接采用二分做就好了
     *
     * @param bloomDay
     * @param m
     * @param k
     * @return
     */
    public int minDays(int[] bloomDay, int m, int k) {
        if (m * k > bloomDay.length) {
            return -1;
        }

        int low = Arrays.stream(bloomDay).min().getAsInt();
        int high = Arrays.stream(bloomDay).max().getAsInt();
        int mid;
        while (low < high) {
            mid = low + ((high - low) >> 1);//可以达到条件 low==high
            if (check(bloomDay, m, k, mid)) {
                high = mid ;
            } else {
                low = mid + 1;//为了解决两个数相邻时，导致死循环
            }
        }
        return high;
    }

    public boolean check(int[] bloomDay, int m, int k, int threshold) {
        int tmpKNum = 0;
        for (int i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i] <= threshold) {
                tmpKNum++;
            }else{
                tmpKNum= 0;
            }
            if (tmpKNum == k) {
                m--;
                tmpKNum = 0;
                if (m == 0) {
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 超时，想复杂了
     *
     * @param bloomDay
     * @param m
     * @param k
     * @return
     */
    public int minDays1(int[] bloomDay, int m, int k) {
        if (m * k > bloomDay.length) {
            return -1;
        }

        int[][] result = new int[2][bloomDay.length];
        for (int j = 0; j < 2; j++) {
            for (int i = 0; i < bloomDay.length; i++) {
                result[j][i] = -1;
            }
        }

        int tmpMax = 0;
        for (int i = 0; i < k; i++) {
            if (bloomDay[i] > tmpMax) {
                tmpMax = bloomDay[i];
            }
        }

        for (int i = 0; i < k; i++) {
            result[0][i] = tmpMax;
        }
        for (int i = k; i < bloomDay.length; i++) {
            int tmp = 0;
            for (int j = 0; j < k; j++) {
                if (bloomDay[i - j] > tmp) {
                    tmp = bloomDay[i - j];
                }
            }
            if (tmpMax < tmp) {
                result[0][i] = tmpMax;
            } else {
                result[0][i] = tmp;
                tmpMax = tmp;
            }
        }

        for (int j = 1; j < m; j++) {
            for (int i = k * (j + 1) - 1; i < bloomDay.length; i++) {
                int tmp = 0;
                for (int q = 0; q < k; q++) {
                    if (bloomDay[i - q] > tmp) {
                        tmp = bloomDay[i - q];
                    }
                }

                int preX = i - k;
                if (preX < 0) {
                    result[j % 2][i] = -1;
                } else {
                    int preResult = result[j % 2][i - 1];
                    result[j % 2][i] = Math.min(Math.max(tmp, result[(j - 1) % 2][preX] == -1 ? Integer.MIN_VALUE : result[(j - 1) % 2][preX]), preResult == -1 ? Integer.MAX_VALUE : preResult);
                }
            }
            for (int i = k * (j + 1) - 1; i < bloomDay.length; i++) {
                result[(j - 1) % 2][i] = -1;
            }
        }
        return result[(m - 1) % 2][bloomDay.length - 1];
    }

}
